#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;
const int N = 32010, M = 70, V = 10010;

int v, w, book;
int n, m;
PII master[M];// 主件

vector<PII> child[M]; // 附件
vector<PII> group[M]; // 对应的分组背包 v w
int f[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i ++ )
    {
        scanf("%d%d%d", &v, &w, &book);
        if (!book) master[i] = {v, w * v};
        else child[book].push_back({v, v * w});
    }
    int cnt = 1;
    for (int i = 1; i <= m; i ++ )
    {
        if (master[i].first)
        {
            // 二进制优化
            for (int k = 0; k < 1 << child[i].size(); k ++ )
            {
                int t1 = master[i].first, t2 = master[i].second;
                for (int u = 0; u < child[i].size(); u ++ )
                    if (k >> u & 1)
                    {
                        t1 += child[i][u].first;
                        t2 += child[i][u].second;
                    }
                group[cnt].push_back({t1, t2});
            }
            cnt ++ ;
        }
    }
    cnt -- ;
    for (int i = 1; i <= cnt; i ++ )
        for (int j = n; j >= 0; j -- )
            for (int k = 0; k < group[i].size(); k ++ )
                if (j >= group[i][k].first)
                    f[j] = max(f[j], f[j - group[i][k].first] + group[i][k].second);
    cout << f[n] << endl;
    return 0;
}
